Solution

---

Overview

Prerequisites

There are three DFS ways to traverse the tree: preorder, postorder and inorder. Please check two minutes picture explanation, if you don't remember them quite well: here is Python version and here is Java version.

Optimal Strategy to Solve the Problem

Root-to-left traversal is so-called DFS preorder traversal. To implement it, one has to follow straightforward strategy Root->Left->Right.

Since one has to visit all nodes, the best possible time complexity here is linear. Hence all interest here is to improve the space complexity.

There are 3 ways to implement preorder traversal: iterative, recursive and Morris.

Iterative and recursive approaches here do the job in one pass, but they both need up to $\mathcal{O}(H)$ space to keep the stack, where $H$ is a tree height.

Morris approach is two-pass approach, but it's a constant-space one.

---

Approach 1: Iterative Preorder Traversal.

Intuition

Here we implement standard iterative preorder traversal with the stack:

• Push root into stack.

• While stack is not empty:

  • Pop out a node from stack and update the current number.

  • If the node is a leaf, update root-to-leaf sum.

  • Push right and left child nodes into stack.

• Return root-to-leaf sum.

Implementation

Note, that Javadocs recommends to use ArrayDeque, and not Stack as a stack implementation.

Complexity Analysis

• Time complexity: $\mathcal{O}(N)$ since one has to visit each node.

• Space complexity: up to $\mathcal{O}(H)$ to keep the stack, where $H$ is a tree height.
  
  
  

---

Approach 2: Recursive Preorder Traversal.

Iterative approach 1 could be converted into recursive one.

Recursive preorder traversal is extremely simple: follow Root->Left->Right direction, i.e. do all the business with the node (= update the current number and root-to-leaf sum), and then do the recursive calls for the left and right child nodes.

P.S. Here is the difference between preorder and the other DFS recursive traversals. On the following figure the nodes are numerated in the order you visit them, please follow 1-2-3-4-5 to compare different DFS strategies implemented as recursion.

Implementation

Complexity Analysis

• Time complexity: $\mathcal{O}(N)$ since one has to visit each node.

• Space complexity: up to $\mathcal{O}(H)$ to keep the recursion stack, where $H$ is a tree height.
  
  
  

---

Approach 3: Morris Preorder Traversal.

We discussed already iterative and recursive preorder traversals, which both have great time complexity though use up to $\mathcal{O}(H)$ to keep the stack. We could trade in performance to save space.

The idea of Morris preorder traversal is simple: to use no space but to traverse the tree.

How that could be even possible? At each node one has to decide where to go: to the left or tj the right, traverse the left subtree or traverse the right subtree. How one could know that the left subtree is already done if no additional memory is allowed?

The idea of Morris algorithm is to set the temporary link between the node and its predecessor: predecessor.right = root. So one starts from the node, computes its predecessor and verifies if the link is present.

• There is no link? Set it and go to the left subtree.

• There is a link? Break it and go to the right subtree.

There is one small issue to deal with : what if there is no left child, i.e. there is no left subtree? Then go straightforward to the right subtree.

Implementation

Complexity Analysis

• Time complexity: $\mathcal{O}(N)$.

• Space complexity: $\mathcal{O}(1)$.
  
  

public int sumNumbers(TreeNode root) {
    return sumNumbers(root, 0);
}

int sumNumbers(TreeNode root, int sum) {
    if (root == null) return 0;
    
    sum = sum*10 + root.val;
    if (root.left == null && root.right == null)
        return sum;
    
    return sumNumbers(root.left, sum) + sumNumbers(root.right, sum);
}

def sumNumbers(self, root: TreeNode) -> int:
        if root is None:
            return 0
        q = deque()
        
        q.append((root, root.val))
        total = 0
        while q:
            
            node, path_sum = q.popleft()
            print(path_sum)
            if node.left is None and node.right is None:
                total += path_sum
                
            if node.left is not None:
                q.append((node.left, path_sum*10+node.left.val))
            if node.right is not None:
                q.append((node.right, path_sum*10+node.right.val))
                    
        return total

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        ans = 0
        total = 0
        
        def dfs(node=root):
            nonlocal ans, total
            if not node:
                return
            total = total * 10 + node.val
            if not node.left and not node.right:
                ans += total
            else:
                dfs(node.left)
                dfs(node.right)
            total = (total - node.val) // 10
        
        dfs()
        return ans